package main.LeetCode75.Level2;

import java.util.*;

public class Day16_Day20 {
    public static void main(String[] args) {
        System.out.println("**************************Day16**************************");
        System.out.println("Question232：用栈实现队列");
        System.out.println("Question155：最小栈");
        System.out.println("Question208：实现 Trie (前缀树)");
        System.out.println("**************************Day17**************************");
        System.out.println("Question57：插入区间");
        System.out.println("Question56：合并区间");
        System.out.println("**************************Day18**************************");
        System.out.println("Question735：行星碰撞");
        System.out.println("Question227：基本计算器 II");
        System.out.println("**************************Day19**************************");
        System.out.println("Question547：省份数量");
        System.out.println("Question947：移除最多的同行或同列石头");
        System.out.println("**************************Day20**************************");
        System.out.println("Question39：组合总和");
        System.out.println("Question46：全排列");
    }
}

class Question232{
    Stack<Integer> major,assist;
    public Question232() {
        major=new Stack<>();
        assist=new Stack<>();
    }

    public void push(int x) {
        major.add(x);
    }

    public int pop() {
        while (major.size()>1){
            assist.add(major.pop());
        }
        int top=major.pop();
        while (!assist.isEmpty()){
            major.add(assist.pop());
        }
        return top;
    }

    public int peek() {
        while (major.size()>1){
            assist.add(major.pop());
        }
        int top=major.peek();
        while (!assist.isEmpty()){
            major.add(assist.pop());
        }
        return top;
    }

    public boolean empty() {
        return major.isEmpty();
    }
}

class Question155{
    Stack<Integer> stack;
    Stack<Integer> assStack;
    public Question155() {
        this.stack=new Stack<>();
        this.assStack=new Stack<>();
        assStack.add(Integer.MAX_VALUE);
    }

    public void push(int val) {
        int min=assStack.peek();//辅助栈中的栈顶元素，即是当前栈中最小值
        if (val<min) assStack.add(val);//入栈元素小于最小元素，则辅助栈中压入val
        else assStack.add(min);//反之再次压入最小元素
        stack.add(val);
    }

    public void pop() {
        stack.pop();
        assStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return assStack.peek();
    }
}

class Trie{
    Trie[] children;
    boolean isEnd;
    public Trie() {
        children=new Trie[26];
        isEnd=false;
    }

    public void insert(String word) {
        Trie node=this;
        char[] str=word.toCharArray();
        for (int i=0;i<str.length;i++){
            int index=str[i]-'a';
            if (node.children[index]==null) node.children[index]=new Trie();
            node=node.children[index];
        }
        node.isEnd=true;
    }

    public boolean search(String word) {
        Trie node=searchPrefix(word);
        return node!=null&&node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix)!=null;
    }

    public Trie searchPrefix(String prefix){
        Trie node=this;
        char[] str=prefix.toCharArray();
        for (int i=0;i<str.length;i++){
            int index=str[i]-'a';
            if (node.children[index]==null) return null;
            node=node.children[index];
        }
        return node;
    }
}

class Question57{
    public int[][] process(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (x, y)-> x[0] - y[0]);
        int l = intervals[0][0], r = intervals[0][1];
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] > r){
                res.add(new int[]{l, r});
                l = intervals[i][0];
                r = intervals[i][1];
            }else{
                r = Math.max(r, intervals[i][1]);
            }
        }
        res.add(new int[]{l, r});
        return res.toArray(new int[0][]);
    }
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int length= intervals.length;
        int[][] newIntervals=new int[length+1][2];
        for (int i=0;i<length;i++) newIntervals[i]=intervals[i];
        newIntervals[length]=newInterval;
        return process(newIntervals);
    }
}

class Question56{
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (x, y)-> x[0] - y[0]);
        int l = intervals[0][0], r = intervals[0][1];
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] > r){
                res.add(new int[]{l, r});
                l = intervals[i][0];
                r = intervals[i][1];
            }else{
                r = Math.max(r, intervals[i][1]);
            }
        }
        res.add(new int[]{l, r});
        return res.toArray(new int[0][]);
    }
}

class Question735{
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> deque=new LinkedList<>();
        int i=asteroids.length-1;
        while (i>=0){
            if (deque.isEmpty()||deque.peekFirst()>0){//队首为空或为正数
                deque.addFirst(asteroids[i]);
            }else {//队首为负数
                int temp=deque.peekFirst();
                if (asteroids[i]<0){//新入队元素为负数
                    deque.addFirst(asteroids[i]);
                }else {//新入队元素为正数
                    if (temp+asteroids[i]==0){//大小相同
                        deque.pollFirst();
                    }else {//大小不同
                        while (temp<0&&temp+asteroids[i]>0){
                            deque.pollFirst();
                            if (!deque.isEmpty()) temp=deque.peekFirst();
                            else break;
                        }
                        if ((temp>0&&temp+asteroids[i]!=0)||deque.isEmpty()) deque.addFirst(asteroids[i]);
                        else if (temp+asteroids[i]==0) deque.pollFirst();
                    }
                }
            }
            i--;
        }
        int[] result=new int[deque.size()];
        for (int j=0;j< result.length;j++){
            result[j]=deque.pollFirst();
        }
        return result;
    }
}

class Question227{
    public int calculate(String s) {//
        int result=0;
        char[] str=s.toCharArray();
        StringBuffer processS=new StringBuffer();
        for (char c:str)//去除空格
            if (c!=' ') processS.append(c);
        str=processS.toString().toCharArray();
        Stack<String> stack=new Stack<>();
        StringBuffer num=new StringBuffer();
        char preOpt='+';
        for (int i=0;i<str.length;i++){
            if (str[i]>='0'&&str[i]<='9') num.append(str[i]);//数字累加
            else{
                switch (preOpt){
                    case '+':
                        stack.add(num.toString());
                        break;
                    case '-':
                        stack.add("-"+num.toString());
                        break;
                    case '*':
                        stack.add(String.valueOf(Integer.valueOf(stack.pop())*Integer.valueOf(num.toString())));
                        break;
                    case '/':
                        stack.add(String.valueOf(Integer.valueOf(stack.pop())/Integer.valueOf(num.toString())));
                        break;
                }
                preOpt=str[i];
                num.delete(0,num.length());
            }
        }
        switch (preOpt){//最后一个数
            case '+':
                stack.add(num.toString());
                break;
            case '-':
                stack.add("-"+num.toString());
                break;
            case '*':
                stack.add(String.valueOf(Integer.valueOf(stack.pop())*Integer.valueOf(num.toString())));
                break;
            case '/':
                stack.add(String.valueOf(Integer.valueOf(stack.pop())/Integer.valueOf(num.toString())));
                break;
        }
        while (!stack.isEmpty()){
            result+=Integer.valueOf(stack.pop());
        }
        return result;
    }
}

class Question547{
    public int findCircleNum(int[][] isConnected) {
        int cities = isConnected.length;
        boolean[] visited = new boolean[cities];
        int provinces = 0;
        for (int i = 0; i < cities; i++) {
            if (!visited[i]) {
                process(isConnected, visited, cities, i);
                provinces++;
            }
        }
        return provinces;
    }

    public void process(int[][] isConnected, boolean[] visited, int cities, int i) {
        for (int j = 0; j < cities; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                process(isConnected, visited, cities, j);
            }
        }
    }
}

class Question947{
    public int removeStones(int[][] stones) {
        int n = stones.length;
        Map<Integer,Integer> parent = new HashMap<>();
        for(int i=0;i<n;i++){
            int[] stone = stones[i];
            int x = stone[0]+10000; //横坐标区别开纵坐标，加100000，不会有歧义
            while(x != parent.getOrDefault(x,x)) x = parent.get(x);
            int y = stone[1];
            if(!parent.containsKey(y)) parent.put(y,y);
            while(y != parent.get(y)) y = parent.get(y);
            if(x == y) continue;
            parent.put(x,y);
        }
        int left =0; //取圈子数即可
        for(Map.Entry<Integer,Integer> entry:parent.entrySet()){
            if(entry.getKey().equals(entry.getValue())){
                left++;
            }
        }
        return n-left;
    }
}

class Question39{
    List<List<Integer>> list=new ArrayList<>();
    public void process(int[] candidates,int cur,List<Integer> curList,int start){
        if (cur==0) {
            list.add(curList);
            return;
        }
        if (cur<0) return;
        for (int i=start;i< candidates.length;i++){
            List<Integer> tempList=new ArrayList<>(curList);
            tempList.add(candidates[i]);
            process(candidates,cur-candidates[i],tempList,i);
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> curList=new ArrayList<>();
        process(candidates,target,curList,0);
        return list;
    }
}

class Question46{
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }
        int n = nums.length;
        process(n, output, res, 0);
        return res;
    }
    public void process(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            process(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }
}